import java.util.PriorityQueue;

// 这个类包含了两个方法来解决将数组和减半的最少操作次数问题
// 测试链接 : https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/
public class Code03_MinimumOperationsToHalveArraySum {

    // 提交时把halveArray1改名为halveArray
    // 这个方法使用PriorityQueue（优先队列，这里配置为大根堆）来解决问题
    public static int halveArray1(int[] nums) {
        // 大根堆，用于存储数组中的元素（转换为double类型）
        // 这里使用lambda表达式定义比较器，使得队列按照元素从大到小排序
        PriorityQueue<Double> heap = new PriorityQueue<>((a, b) -> b.compareTo(a));
        double sum = 0;
        // 遍历数组，将每个元素添加到堆中，并计算数组元素的总和
        for (int num : nums) {
            heap.add((double) num);
            sum += num;
        }
        // 将总和除以2，得到要减少到的目标值
        sum /= 2;
        int ans = 0;
        // 只要减少的值还没有达到目标值
        for (double minus = 0, cur; minus < sum; ans++, minus += cur) {
            // 取出堆顶元素（当前最大元素），将其减半
            cur = heap.poll() / 2;
            // 再将减半后的元素放回堆中
            heap.add(cur);
        }
        return ans;
    }

    public static int MAXN = 100001;
    public static long[] heap = new long[MAXN];
    public static int size;

    // 提交时把halveArray2改名为halveArray
    // 这个方法使用自定义的堆结构（数组表示的堆）来解决问题
    public static int halveArray2(int[] nums) {
        // 初始化堆的大小为数组的长度
        size = nums.length;
        long sum = 0;
        // 从数组的最后一个元素开始，将每个元素左移20位（相当于乘以2的20次方）后存入堆数组
        // 同时计算数组元素的总和
        for (int i = size - 1; i >= 0; i--) {
            heap[i] = (long) nums[i] << 20;
            sum += heap[i];
            // 对每个加入堆的元素进行堆化操作，以维护堆的性质
            heapify(i);
        }
        // 将总和除以2，得到要减少到的目标值
        sum /= 2;
        int ans = 0;
        // 只要减少的值还没有达到目标值
        for (long minus = 0; minus < sum; ans++) {
            // 将堆顶元素（最大元素）减半
            heap[0] /= 2;
            // 更新已经减少的值
            minus += heap[0];
            // 对堆顶元素进行堆化操作，以维护堆的性质
            heapify(0);
        }
        return ans;
    }

    // 这个方法用于对指定位置的元素进行堆化操作
    // 目的是维护堆的性质（这里是大根堆性质）
    public static void heapify(int i) {
        int l = i * 2 + 1;
        // 只要左子节点存在（即l < size）
        while (l < size) {
            // 确定左右子节点中的较大值
            int best = l + 1 < size && heap[l + 1] > heap[l]? l + 1 : l;
            // 确定当前节点和较大子节点中的最大值
            best = heap[best] > heap[i]? best : i;
            // 如果当前节点已经是最大的，不需要调整，直接退出
            if (best == i) {
                break;
            }
            // 交换当前节点和较大值节点
            swap(best, i);
            // 更新当前节点的索引为交换后的节点索引
            i = best;
            // 更新左子节点的索引
            l = i * 2 + 1;
        }
    }

    // 这个方法用于交换堆数组中两个指定位置的元素
    public static void swap(int i, int j) {
        long tmp = heap[i];
        heap[i] = heap[j];
        heap[j] = tmp;
    }
}